Search results for "discrete [space-time]"

Longest Motifs with a Functionally Equivalent Central Block

2004

International audience; This paper presents a generalization of the notion of longest repeats with a block of k don't care symbols introduced by [Crochemore et al., LATIN 2004] (for k fixed) to longest motifs composed of three parts: a first and last that parameterize match (that is, match via some symbol renaming, initially unknown), and a functionally equivalent central block. Such three-part motifs are called longest block motifs. Different types of functional equivalence, and thus of matching criteria for the central block are considered, which include as a subcase the one treated in [Crochemore et al., LATIN 2004] and extend to the case of regular expressions with no Kleene closure or …

The Steiner Traveling Salesman Problem and its extensions

2019

Abstract This paper considers the Steiner Traveling Salesman Problem, an extension of the classical Traveling Salesman Problem on an incomplete graph where not all vertices have demand. Some extensions including several depots or location decisions are introduced, modeled and solved. A compact integer linear programming formulation is proposed for each problem, where the routes are represented with two-index decision variables, and parity conditions are modeled using cocircuit inequalities. Exact branch-and-cut algorithms are developed for all formulations. Computational results obtained confirm the good performance of the algorithms. Instances with up to 500 vertices are solved optimally.

Distance graphs and the T-coloring problem

1999

Abstract The T-coloring problem is, given a graph G = (V, E), a set T of nonnegative integers containing 0, and a ‘span’ bound s ⩾ 0, to compute an integer coloring f of the vertices of G such that |f(ν) − f(w)| ∉ T ∀νw ∈ E and max f − min f ⩽ s. This problem arises in the planning of channel assignments for broadcast networks. When restricted to complete graphs, the T-coloring problem boils down to a number problem which can be solved efficiently for many types of sets T. The paper presents results indicating that this is not the case if the set T is arbitrary. To these ends, the class of distance graphs is introduced, which consists of all graphs G : G ≅ G(A) for some (finite) set of posi…

Thin and fat sets for doubling measures in metric spaces

2011

We consider sets in uniformly perfect metric spaces which are null for every doubling measure of the space or which have positive measure for all doubling measures. These sets are called thin and fat, respectively. In our main results, we give sufficient conditions for certain cut-out sets being thin or fat.

A function whose graph has positive doubling measure

2014

We show that a doubling measure on the plane can give positive measure to the graph of a continuous function. This answers a question by Wang, Wen and Wen. Moreover we show that the doubling constant of the measure can be chosen to be arbitrarily close to the doubling constant of the Lebesgue measure.

Planar maps whose second iterate has a unique fixed point

2007

Let a>0, F: R^2 -> R^2 be a differentiable (not necessarily C^1) map and Spec(F) be the set of (complex) eigenvalues of the derivative F'(p) when p varies in R^2. (a) If Spec(F) is disjoint of the interval [1,1+a[, then Fix(F) has at most one element, where Fix(F) denotes the set of fixed points of F. (b) If Spec(F) is disjoint of the real line R, then Fix(F^2) has at most one element. (c) If F is a C^1 map and, for all p belonging to R^2, the derivative F'(p) is neither a homothety nor has simple real eigenvalues, then Fix(F^2) has at most one element, provided that Spec(F) is disjoint of either (c1) the union of the number 0 with the intervals ]-\infty, -1] and [1,\infty[, or (c2) t…

Fixed Points in Topological *-Algebras of Unbounded Operators

2001

We discuss some results concerning fixed point equations in the setting of topological *-algebras of unbounded operators. In particular, an existence result is obtained for what we have called {\em weak $\tau$ strict contractions}, and some continuity properties of these maps are discussed. We also discuss possible applications of our procedure to quantum mechanical systems.

The Spectrum of Analytic Mappings of Bounded Type

2000

Abstract A Banach space E is said to be (symmetrically) regular if every continuous (symmetric) linear mapping from E to E ′ is weakly compact. For a complex Banach space E and a complex Banach algebra F , let H b ( E ,  F ) denote the algebra of holomorphic mappings from E to F which are bounded on bounded sets. We endow H b ( E ,  F ) with the usual Frechet topology. M ( H b ( E ,  F ),  F ) denotes the set of all non-null continuous homomorphisms from H b ( E ,  F ) to F . A subset of G EF on which the extension of Zalduendo is multiplicative is presented and it is shown that, in general, the sets G EF and M ( H b ( E ,  F ),  F ) do not coincide. We prove that if E is symmetrically regu…

Simple and semisimple Lie algebras and codimension growth

1999

Irreducible finitary Lie algebras over fields of positive characteristic

2000

A Lie subalgebra L of [gfr ][lfr ][ ](V) is said to be finitary if it consists of elements of finite rank. We study the situation when L acts irreducibly on the infinite-dimensional vector space V and show: if Char [ ] > 7, then L has a unique minimal ideal I. Moreover I is simple and L/I is solvable.